/*
题目链接：https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/description/
题目标题：最大为N的数字组合
提交时间：2024/10/7
*/

//每一位进行分析
class Solution {
 public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        string str=to_string(n);   //转为字符串，便于每个位进行比较
        int d=digits.size();
        int s=str.size();
        //long long dp[s+1][2];   //从1开始(为啥不行？)
        vector<vector<int>>dp(s+1,vector<int>(2));   //s+1行，每行2列
        dp[0][1]=1;
        for(int i=1;i<=s;i++){           //对数字n的每一位进行分析
            for(int j=0;j<d;j++){        //遍历digits中所有的元素
                if(digits[j][0]==str[i-1]){dp[i][1]=dp[i-1][1];}  
                else if(digits[j][0]<str[i-1]){dp[i][0]+=dp[i-1][1];}   //加上dp[i-1][1]，其中dp[i-1][1]可能为0，若为0 说明不用加上，不然会超过
                else break;   //说明接下来都会大，所以跳出循环
            }
            if(i>1){dp[i][0]=dp[i][0]+d+dp[i-1][0]*d;}  //组合数学，每一位的可能值为d种，i>1开始（至少2位数才能开始）,加上dp[i][0] 表示加上前面求的所有值
        }
        return dp[s][0]+dp[s][1];  //前s位小于数字n+前s位等于数字n的所有值相加
    }
 };